#include <bits/stdc++.h>
using namespace std;

int lis(vector<int> v) {
    vector<int> dp(v.size(), 1);

    for(int i = 1; i < v.size(); i++)
        for(int j = 0; j < i; j++)
            if (v[j] < v[i])
                dp[i] = max(dp[i], dp[j] + 1);
    return *max_element(dp.begin(), dp.end());
}

int main() {
    assert(lis({3, 10, 2, 1, 20}) == 3);
    assert(lis({30, 20, 10}) == 1);
    assert(lis({2, 2, 2}) == 1);
    assert(lis({10, 20, 35, 80}) == 4);
}
